import java.io.PrintStream;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map.Entry;
import java.util.TreeSet;

public class APriori {

	private ArrayList<TreeSet<String>> itemsets;

	private ArrayList<HashMap<TreeSet<String>, Integer>> largesets;

	private double sup, conf;

	private int ttlTxns;

	public APriori(List<String> txns, String delimiter, double sup, double conf) {
		this.sup = sup;
		this.conf = conf;
		this.itemsets = new ArrayList<TreeSet<String>>();
		this.ttlTxns = txns.size();

		HashMap<String, Integer> counts = new HashMap<String, Integer>();

		for (String txn : txns) {
			String[] items = txn.split(delimiter);
			TreeSet<String> itemset = new TreeSet<String>();
			for (String item : items) {
				if(!item.isEmpty())
				{
					itemset.add(item);
					if (!counts.containsKey(item))
						counts.put(item, 1);
					else
						counts.put(item, counts.get(item) + 1);
				}
			}

			this.itemsets.add(itemset);
		}

		largesets = new ArrayList<HashMap<TreeSet<String>, Integer>>();

		// add null as L0, never used
		largesets.add(null);

		// prepare L1
		HashMap<TreeSet<String>, Integer> l1 = new HashMap<TreeSet<String>, Integer>();
		for (Entry<String, Integer> entry : counts.entrySet()) {
			TreeSet<String> tset = new TreeSet<String>();
			tset.add(entry.getKey());
			l1.put(tset, entry.getValue());
		}
		largesets.add(l1);
		checkMinSup(1);
	}

	public List<Rule> getRules() {
		ArrayList<Rule> result = new ArrayList<Rule>();

		for (int k = 2; k < largesets.size(); k++) {
			HashMap<TreeSet<String>, Integer> prevL = largesets.get(k - 1);
			HashMap<TreeSet<String>, Integer> curL = largesets.get(k);

			for (Entry<TreeSet<String>, Integer> entry : curL.entrySet()) {
				for (String rhs : entry.getKey()) {
					@SuppressWarnings("unchecked")
					TreeSet<String> lhs = (TreeSet<String>) entry.getKey()
							.clone();
					lhs.remove(rhs);

					double conf = (double) entry.getValue() / prevL.get(lhs);
					if (conf >= this.conf) {
						double sup = (double) entry.getValue() / ttlTxns;
						result.add(new Rule(lhs, rhs, sup, conf));
					}
				}
			}
		}

		return result;
	}

	public void printLargeSets() {
		PrintStream out = System.out;
		for (int i = 1; i < largesets.size(); i++) {
			out.println("L" + i + ":");
			HashMap<TreeSet<String>, Integer> largeset = largesets.get(i);

			for (Entry<TreeSet<String>, Integer> entry : largeset.entrySet()) {
				out.print('[');
				for (String item : entry.getKey()) {
					out.print(item);
					if (!item.equals(entry.getKey().last()))
						out.print(',');
				}
				out.print("] ");
				out.format("%2.2f%%\n", (double) entry.getValue() / ttlTxns
						* 100);
			}
		}
	}

	public void fillLargeSets() {
		for (int k = 2; !largesets.get(k - 1).isEmpty(); k++) {
			aprioriGen(k);

			countFrequency(k);

			checkMinSup(k);
		}

		// Last large set guaranteed to be empty
		largesets.remove(largesets.size() - 1);
	}

	private void checkMinSup(int k) {
		HashMap<TreeSet<String>, Integer> c = largesets.get(k);
		HashSet<TreeSet<String>> removeSet = new HashSet<TreeSet<String>>();
		for (Entry<TreeSet<String>, Integer> entry : c.entrySet()) {
			if ((double) entry.getValue() / ttlTxns < sup)
				removeSet.add(entry.getKey());
		}

		for (TreeSet<String> key : removeSet)
			c.remove(key);
	}

	private void countFrequency(int k) {
		HashMap<TreeSet<String>, Integer> c = largesets.get(k);

		if (c.isEmpty())
			return;

		for (TreeSet<String> itemset : itemsets) {
			for (Entry<TreeSet<String>, Integer> entry : c.entrySet()) {
				if (itemset.containsAll(entry.getKey()))
					entry.setValue(entry.getValue() + 1);
			}
		}
	}

	private void aprioriGen(int k) {
		if (largesets.size() < k || largesets.get(k - 1).isEmpty())
			return;

		HashMap<TreeSet<String>, Integer> prevL = largesets.get(k - 1);

		HashMap<TreeSet<String>, Integer> c = new HashMap<TreeSet<String>, Integer>();

		for (TreeSet<String> p : prevL.keySet())
			for (TreeSet<String> q : prevL.keySet())
				if (isMatch(p, q)) {
					@SuppressWarnings("unchecked")
					TreeSet<String> newset = (TreeSet<String>) p.clone();
					newset.add(q.last());
					c.put(newset, 0);
				}

		largesets.add(c);

		prune(k);
	}

	private void prune(int k) {
		HashMap<TreeSet<String>, Integer> c = largesets.get(k);
		HashMap<TreeSet<String>, Integer> prevL = largesets.get(k - 1);
		HashSet<TreeSet<String>> removeSet = new HashSet<TreeSet<String>>();

		for (TreeSet<String> key : c.keySet()) {
			for (String item : key) {
				@SuppressWarnings("unchecked")
				TreeSet<String> clone = (TreeSet<String>) key.clone();
				clone.remove(item);
				if (!prevL.containsKey(clone)) {
					removeSet.add(key);
					break;
				}
			}
		}

		for (TreeSet<String> key : removeSet)
			c.remove(key);
	}

	private boolean isMatch(TreeSet<String> p, TreeSet<String> q) {
		if (p.size() != q.size())
			return false;

		Iterator<String> ip = p.iterator();
		Iterator<String> iq = q.iterator();

		for (int i = 0; i < p.size() - 1; i++)
			if (!ip.next().equals(iq.next()))
				return false;

		return ip.next().compareTo(iq.next()) < 0;
	}
}

class Rule {
	public TreeSet<String> lhs;
	public String rhs;
	public double sup, conf;

	public Rule(TreeSet<String> lhs, String rhs, double sup, double conf) {
		this.lhs = lhs;
		this.rhs = rhs;
		this.sup = sup;
		this.conf = conf;
	}

	@Override
	public String toString() {
		StringBuffer out = new StringBuffer();

		out.append('[');
		for (String item : lhs) {
			out.append(item);
			if (!item.equals(lhs.last()))
				out.append(',');
		}
		out.append("] => [");
		out.append(rhs);
		out.append("] (Conf: ");
		out.append(String.format("%2.2f%%", conf * 100));
		out.append(", Supp: ");
		out.append(String.format("%2.2f%%", sup * 100));
		out.append(')');

		return out.toString();
	}
}